Fundamental Theorem of Arithmetic

Note that by taking $1$ as an empty product we can extend this result to $n\ge 1$.

To prove this we will first prove a weaker result with non-uniqueness.

Proof

We proceed with strong induction as follows. First note that because $2$ is prime, $2$ is expressible as a product of primes.

Now assume than for all $k$ satisfying $2\le k\le n-1$, $k$ can be written as a product of primes.

Suppose $n$ is prime, then clearly it is a singleton product of primes. If $n$ is not prime, then it factors as $n=ab$ where $1<a,b<n$. Applying the hypothesis to $k=a$ and $k=b$ we have

where all $p_i$ and $q_j$ are prime. Therefore

a product of primes.

We can now prove uniqueness.

Proof

Assume that $n=p_1\dots p_k=q_1\dots q_s$ are two factorisations of $n$ into a product of primes. Then $p_i\mid q_1\dots q_s$ for each $i$, and so by Euclid's lemma we know that $p_i$ divides one of $q_1,\dots ,q_s$, say $q_j$. However the only divisors of $q_j$ are $1$ and $p_i$, and $p_i\ne 1$ by assumption that it is prime. Hence $p_i=q_j$.

Repeating this procedure and removing factors, we are able to pair them uniquely, and also conclude that $s=k$.